Leetcode刷题记录(Java)

Problem 700 Search in a Binary Search Tree

在二叉树中找到满足值要求的子树,若找不到则返回null

---

主要思路:
该题的思路比较直接,就是找到与值相等的结点即可,而对于二叉搜索树,自然是比值大往左走,比值小往右走,不过这里特别要注意的是,该题只需要返回结点即可,不需要重建树,所以在返回位置的选择上需要特别注意.遇到符合要求的结点直接返回

---

代码实现:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode searchBST(TreeNode root, int val) {
        if (root==null)
            return null;
        else {
            if (root.val==val){
                return root;
            }else if (root.val<val){
                return searchBST(root.right,val);
            }else {
                return searchBST(root.left,val);
            }
        }
    }
}

---

⭐Problem 703 Kth Largest Element in a Stream

找出数组中第K大的数字,该数组为乱序且容量不断增加,每次都要返回其第K大的值.

---

主要思路:
提到第K大的值一般会想到堆排序,在Java中的实现为PriorityQueue,只需要不断添加数字,当queue大小超过K的时候出队列,最后返回队头元素即可

---

代码实现:

class KthLargest {
    private Queue<Integer> pq;
    private int k;

    public KthLargest(int k, int[] nums) {
        pq = new PriorityQueue<>(k);
        this.k = k;
        for (int num : nums) {
            add(num);
        }
    }

    public int add(int val) {
        pq.add(val);
        if (pq.size() == k + 1) {
            pq.remove();
        }
        return pq.peek();
    }
}

/**
 * Your KthLargest object will be instantiated and called as such:
 * KthLargest obj = new KthLargest(k, nums);
 * int param_1 = obj.add(val);
 */

---

⭐Problem 746 Min Cost Climbing Stairs

找出登上楼顶的最小代价,你可以选择每次跳一步或者两步,起点可以为第一个台阶或者第二个台阶.

---

主要思路:
这就是一个跳台阶问题,最原始的跳台阶问题是求总共的选择,采用斐波拉契数列求得.此处增加了val,但是总体思想还是DP问题,也就是从第三个台阶开始比较min,是第i-
1个台阶加上当前台阶的值小,还是i-2个台阶加上当前台阶的值小,之后循环得到结果.

---

代码实现:

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        for (int i = 2; i < cost.length; i++){
            cost[i] = Math.min(cost[i-1] + cost[i], cost[i-2] + cost[i]);
        }

        int arrLength = cost.length;
        return Math.min(cost[arrLength - 1], cost[arrLength - 2]);
    }
}

---

代码说明:
由于不管当前是最后一位还是倒数第二位,累加值的工作都已结束,只需要比较两者,取较小的那个即可.